/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张宇田
 * Date: 2025-06-15
 * Time: 12:38
 */
import java.util.Scanner;

public class LCS {
    public static int lcs(String a, String b) {
        return find(a, b, 0, 0);
    }

    private static int find(String a, String b, int i, int j) {
        if (i == a.length() || j == b.length()) return 0;

        System.out.println("比较: " + a.charAt(i) + " 和 " + b.charAt(j));

        if (a.charAt(i) == b.charAt(j)) {
            System.out.println("匹配: " + a.charAt(i) + " 位置 i=" + i + ", j=" + j);
            return 1 + find(a, b, i + 1, j + 1);
        } else {
            int skipA = find(a, b, i + 1, j);
            int skipB = find(a, b, i, j + 1);
            return Math.max(skipA, skipB);
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("输入格式：text1 = \"abcde\", text2 = \"ace\"\n请输入：");
        String line = input.nextLine();

        // 解析输入格式：text1 = "abcde", text2 = "ace"
        String[] parts = line.split(",");
        String text1 = parts[0].split("=")[1].trim().replaceAll("\"", "");
        String text2 = parts[1].split("=")[1].trim().replaceAll("\"", "");

        int result = lcs(text1, text2);
        System.out.println("最长公共子序列长度: " + result);
    }
}


